Jacobi 迭代法

范数

$1$ 范数：向量各分量的绝对值之和。 ${‖ x ‖}_{1} = \sum_{i = 1}^{n} | x_{i} |$
$2$ 范数：向量的模。 ${‖ x ‖}_{2} = \sqrt{\sum_{i = 1}^{n} x_{i}^{2}}$
$\infty$ 范数：向量中绝对值最大的分量。 ${‖ x ‖}_{\infty} = max_{1 \leq i \leq n} | x_{i} |$

列范数：每一列各元素之和的最大一项。 ${‖ A ‖}_{1} = max_{1 \leq j \leq n} \sum_{i = 1}^{n} | a_{i j} |$
行范数：每一行各元素之和的最大一项。 ${‖ A ‖}_{\infty} = max_{1 \leq i \leq n} \sum_{j = 1}^{n} | a_{i j} |$
谱范数：矩阵 $A^{T} A$ 的最大特征值的平方根。 ${‖ A ‖}_{2} = \sqrt{max λ (A^{T} A)}$
$F$ 范数：矩阵 $A$ 所有元素的平方和。 ${‖ A ‖}_{F} = \sqrt{\sum_{i = 1}^{n} \sum_{j = 1}^{n} a_{i j}^{2}}$

原理推导过程

Jacobi 迭代法类似简单迭代法：想办法将 $A x = b$ 转换为 $x = B x + g$ 的形式。

\begin{matrix} {\begin{matrix} a_{11} x_{1} & + a_{12} x_{2} & + a_{13} x_{3} & + a_{14} x_{4} & = b_{1} \\ a_{21} x_{1} & + a_{22} x_{2} & + a_{23} x_{3} & + a_{24} x_{4} & = b_{2} \\ ⋮ \\ a_{n 1} x_{1} & + a_{n 2} x_{2} & + a_{n 3} x_{3} & + a_{n 4} x_{4} & = b_{n} \end{matrix} & \Leftrightarrow & {\begin{matrix} x_{1} & = & - \frac{a_{12} x_{2} + a_{13} x_{3} + \dots + a_{1 n} x_{n}}{a_{11}} & + \frac{b_{1}}{a_{11}} \\ x_{2} & = & - \frac{a_{21} x_{1} + a_{23} x_{3} + \dots + a_{2 n} x_{n}}{a_{22}} & + \frac{b_{2}}{a_{22}} \\ ⋮ \\ x_{n} & = & - \frac{a_{n 1} x_{1} + a_{n 2} x_{2} + \dots + a_{n, n - 1} x_{n - 1}}{a_{n n}} & + \frac{b_{n}}{a_{n n}} \end{matrix} \\ A x = b & \Leftrightarrow & x^{(k + 1)} = B_{J} x^{(k)} + g_{J} \end{matrix}

所以，由

系数矩阵 $A$ ： $[\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}]$
常数向量 $b$ ： $[\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}]$

可以得出：

迭代矩阵 $B_{J}$ ： $[\begin{matrix} 0 & - \frac{a_{12}}{a_{11}} & \dots & - \frac{a_{1 n}}{a_{11}} \\ - \frac{a_{21}}{a_{22}} & 0 & \dots & - \frac{a_{2 n}}{a_{22}} \\ ⋮ & ⋮ & ⋮ \\ - \frac{a_{n 1}}{a_{n n}} & - \frac{a_{n 2}}{a_{n n}} & \dots & 0 \end{matrix}]$
迭代常数向量 $g_{J}$ ： $[\begin{matrix} \frac{b_{1}}{a_{11}} \\ \frac{b_{2}}{a_{22}} \\ ⋮ \\ \frac{b_{n}}{a_{n n}} \end{matrix}]$

或者，可以使用矩阵计算：

由系数矩阵 $A$

[\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}]

可以拆开得到：

下三角矩阵 $L$ ： $[\begin{matrix} 0 \\ a_{21} & 0 \\ ⋮ & ⋮ & ⋱ \\ a_{n 1} & a_{n 2} & \dots & 0 \end{matrix}]$
上三角矩阵 $U$ ： $[\begin{matrix} 0 & a_{12} & \dots & a_{1 n} \\ 0 & \dots & a_{2 n} \\ ⋱ & ⋮ \\ 0 \end{matrix}]$
对角矩阵 $D$ ： $[\begin{matrix} a_{11} \\ a_{22} \\ ⋱ \\ a_{n n} \end{matrix}]$

注意

此处的 $L$ 和 $U$ 与矩阵的 LU 分解中的 $L$ 和 $U$ 不是同个概念！

于是，迭代矩阵 $B_{J}$ 为：

B_{J} = - D^{- 1} (L + U)

常数向量 $g_{J}$ 为：

g_{J} = D^{- 1} b

满足以下条件之一，Jacobi 迭代法对任意初始向量一定收敛：

迭代矩阵 $B_{J}$ 的谱半径 $< 1$ 。